
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution {
//    List<Integer> list = new ArrayList<>();
//    public List<Integer> preorderTraversal(TreeNode root) {
//        if (root == null) {
//            return list;
//        }
//        list.add(root.val);
//        preorderTraversal(root.left);
//        preorderTraversal(root.right);
//        return list;
//    }



    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        list.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = preorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }
    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k) {
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k-1)+ getKLevelNodeCount(root.right, k-1);
    }

    // https://leetcode.cn/problems/valid-parentheses/
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch1 = s.charAt(i);
            if (ch1 == '{' || ch1 == '[' || ch1 == '(') {
                stack.push(ch1);
            } else {
                if (stack.empty()) {
                    return false;
                }
                char ch2 = stack.peek();
                if (ch2=='['&&ch1==']' || ch2=='{'&&ch1=='}' || ch2=='('&&ch1==')') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    public static void main1(String[] args) {
        String str = "()";
        System.out.println(isValid(str));
    }

    // https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int popPose = 0;
        for (int j : pushA) {
            if (j != popA[popPose]) {
                stack.push(j);
            } else {
                popPose++;
                while (true) {
                    if (!stack.empty() && stack.peek() == popA[popPose]) {
                        stack.pop();
                        popPose++;
                    } else {
                        break;
                    }
                }
            }
        }
        while (!stack.empty()) {
            if (stack.pop() != popA[popPose]) {
                return false;
            }
            popPose++;
        }
        return true;
    }

    public static void main2(String[] args) {
        int[] arr1 = {2,1,0};
        int[] arr2 = {1,2,0};
        System.out.println(IsPopOrder(arr1, arr2));
    }

    // https://leetcode.cn/problems/evaluate-reverse-polish-notation/
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (!isOperation(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int right = stack.pop();
                int left = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(left+right);
                        break;
                    case "-":
                        stack.push(left-right);
                        break;
                    case "*":
                        stack.push(left*right);
                        break;
                    case "/":
                        stack.push(left/right);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String str) {
        return str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/");
    }
}